/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 */
public class BinarySearchTree {

    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    public TreeNode root = null;


    /**
     * 查找二叉搜索树中指定的val值
     * @param val
     * @return
     */
    public TreeNode find(int val) {
        return findNode(root, val);
    }

    private TreeNode findNode(TreeNode root, int val){
        if (root == null){
            return null;
        }
        if (val == root.val){
            return root;
        }else if (val > root.val){
            findNode(root.right, val);
        }else if (val < root.val){
            findNode(root.left, val);
        }
        return null;
    }

    /**
     * 插入val 如果已经存在 则不插入
     * @param val
     */
    public void insert(int val){
        if (root == null){
            root = new TreeNode(val);
            return;
        }
        TreeNode cur = root;
        TreeNode parent = null;
        while (cur != null){
            if (val == cur.val){
                return;
            } else if (val > cur.val){
                parent = cur;
                cur = cur.right;
            }else{
                parent = cur;
                cur = cur.left;
            }
        }
        if (val < parent.val){
            parent.left = new TreeNode(val);
        }else{
            parent.right = new TreeNode(val);
        }
    }
}
